1. Field of the Invention
The present invention relates to a branch control circuit used for pipeline processing of instructions, and particularly to a branch control circuit that can minimize confusion caused by branching in the pipeline processing.
2. Description of the Prior Art
These days, many data processors are employing pipeline processing to process and execute instructions at a high speed.
The pipeline processing involves, for example, an instruction fetching stage, an instruction decoding stage, an effective address generating stage, an operand fetching stage, and an instruction executing stage. Instructions are successively read from a memory and sequentially processed through these pipeline stages. Each of the stages processes a different instruction, and if there is no confusion in the flow in the pipeline stages, the system provides maximum performance.
Let us suppose a data processor consumes one machine cycle in each processing stage, it requires five machine cycles for processing one instruction in a data processor without the pipeline system. On the other hand, a data processor employing the pipeline processing can process instructions five times as fast as the non-pipeline processor, because the pipeline processor executes one instruction in each machine cycle if no confusion occurs in the flow of the pipeline processing.
According to a conventional pipeline technique, however, a branch instruction may cause confusion in the pipeline processing. After executing the branch instruction, the processor must invalidate instructions that are following the branch instruction and being processed in the pipeline stages, and restart processing from a target instruction of the branch. This deteriorates the performance of the pipeline.
To deal with the problem, a processor employing a branch prediction method has been proposed. This method predicts whether or not a branch instruction is taken, according to branch prediction information. If the branch instruction is predicted to be taken, the processor starts to process an instruction addressed by the branch instruction before executing the branch instruction, thereby reducing the confusion which occurs in the pipeline.
According to this technique, some means must be provided to find a target address of the branch instruction. One means for finding the address is a look-up table which is referred to in the instruction fetching stage of the pipeline.
FIG. 1 shows flows of instructions in pipeline stages of a conventional branch control circuit employing the look-up table.
The look-up table contains addresses of branch instructions BIs and addresses of target instructions TIs. The look-up table is referred to in the instruction fetching stage or instruction decoding stage of the pipeline to find a target address of a branch instruction BI. If the given branch instruction BI is predicted that branch is taken, an instruction located at a target address obtainable from the look-up table is fetched. This technique may minimize confusion in the pipeline, as shown in FIG. 1, if the branch prediction hits.
The look-up table and its contents inevitably increase, however, the size of hardware. In other words, the number of entries of the look-up table is limited by hardware.
If the number of entries of the look-up table is small, a mis-hit rate will rise in referring to the look-up table. This makes the prediction of a branch instruction BI impossible.
In FIG. 2, flows of a pipeline process with unsuccessful branch prediction are shown. As shown in FIG. 2, since an instruction fetch of the target instructions TIs is carried out after executing the branch instruction BI, the process after the first time requires more four cycles than that at the first time.
In this way, the conventional branching control technique for a pipeline system requires the size of hardware (the size of the look-up table) to be sufficiently large for increasing the hit rate of branch prediction. If the number of entries of the look-up table is small, the mis-hit rate increases to cause confusion in the pipeline.